/*  slftonpr.cpp  by K.Tsuru  */
// function ID 2010   DRADIX    since ver 2.181
#ifndef SN_H
#include "sn.h"
#endif
// for sorting
static int sortBySize(const void *e1, const void *e2) {
    return (int)((const SLong *)e2)->DFigures() - (int)((const SLong *)e1)->DFigures();
}

/**************************************************************************
product is evaluated such as
1) a[0]a[1]...a[n-1] sort in size
2) a[n-2] <-- a[n-2]a[n-1]
3) n <-- n-1
repeat n > 1
**************************************************************************/
SLong TournamentProduct(const SNBlock <SLong>& a, const uint N) {
    if(N == 1) return a(0);

    SLong* r = new SLong[N];

    for(uint i = 0; i < N ; i++) r[i] = a(i);

// preliminary tournament --- while(n > 2^p) n--;
    uint n = N; // > 1
// 1,000,000! time =0.0
    qsort(r, n, sizeof(SLong), sortBySize); // sort into r[0] >= r[1] >= ...
    while(n > 1) {
        r[n-2] = r[n-2]*r[n-1]; // multiply lowest two
        r[n-1].SetZero();       // a loser
        n--;
        qsort(r, n, sizeof(SLong), sortBySize); // arrange in large order

        int ratio = r[0].DFigures()/r[n-1].DFigures();
        if(isPow2(n) && (ratio < 4)) break; // 2, 3 or 4 : 12.8sec , 6 : 13.4
    }
// t1 = 2.3 sec
// the final selection. n = 2^p here.
    while(n > 1) {  // selection of both sides
        uint j;
        for(j = 0; j < n/2; j++) r[j] = r[j]*r[n-j-1];
        n /= 2;
    }
// the champion is the result(^_^)
    SLong R(r[0]);
    delete[] r;
// t2 = 10.0 sec (total 12.8 sec)
    return R;
}